package com.moyoutian.leetcode;

/**
 * 4. 寻找两个正序数组的中位数
 * <p>
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * <p>
 * 输出：2.00000
 * <p>
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * <p>
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * <p>
 * 输出：2.50000
 * <p>
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * <p>
 * <p>
 * 示例 3：
 * <p>
 * 输入：nums1 = [0,0], nums2 = [0,0]
 * <p>
 * 输出：0.00000
 * <p>
 * <p>
 * 示例 4：
 * <p>
 * <p>
 * 输入：nums1 = [], nums2 = [1]
 * <p>
 * 输出：1.00000
 * <p>
 * <p>
 * 示例 5：
 * <p>
 * 输入：nums1 = [2], nums2 = []
 * <p>
 * 输出：2.00000
 * <p>
 * <p>
 * 提示：
 * <p>
 * nums1.length == m
 * <p>
 * nums2.length == n
 * <p>
 * 0 <= m <= 1000
 * <p>
 * 0 <= n <= 1000
 * <p>
 * 1 <= m + n <= 2000
 * <p>
 * -106 <= nums1[i], nums2[i] <= 106
 * <p>
 * <p>
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 * <p>
 * 通过次数544,133提交次数1,328,864
 */
public class Demo4a {

    public static void main(String[] args) {
        int[] nums1 = new int[]{};
        int[] nums2 = new int[]{1};
//        int[] nums1 = new int[]{1, 3};
//        int[] nums2 = new int[]{2, 4};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int len1 = nums1.length;
        int len2 = nums2.length;
        int count = len1 + len2;
        int avg = (count + 1 >> 1);
        int l = 0;
        int r = len1;
        //右半部下标
        int n1r, n2r;
        while (true) {
            n1r = (r + l + 1) >> 1;
            n2r = avg - n1r;
            //左边要取最大值，所以赋值最小值
            int ln1 = n1r == 0 ? Integer.MIN_VALUE : nums1[n1r - 1];
            int ln2 = n2r == 0 ? Integer.MIN_VALUE : nums2[n2r - 1];
            //右边要取最小值，所以赋值最大值
            int rn1 = n1r == len1 ? Integer.MAX_VALUE : nums1[n1r];
            int rn2 = n2r == len2 ? Integer.MAX_VALUE : nums2[n2r];
            // 交差判断
            if (rn1 < ln2) {
                l = n1r;
            } else if (rn2 < ln1) {
                r = n1r - 1;
            } else {
                return (count >> 1 << 1) == count ? (Math.max(ln1, ln2) + Math.min(rn1, rn2)) / 2.0 : Math.max(ln1, ln2);
            }
        }
    }

    public static double findMedianSortedArraysO(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int count = nums1.length + nums2.length;
        //偶数判断。1000 -1 = 111  ，1000&111=0
        //和是否是偶数
        boolean flag = (count >> 1 << 1) == count;
        //左右两边的数量
        int avg = (count + 1 >> 1);
        int n1l = (nums1.length >> 1) - 1;
        int n1r = n1l + 1;

        //奇数多的放在左边
        int n2l = (avg - (n1l + 1)) - 1;
        //数组2的右边数量
        int n2r = n2l + 1;

        //如果小的长度为0就不用考虑小的长度
        if (nums1.length == 0) {
            return flag ? (nums2[n2l] + nums2[n2r]) / 2.0 : nums2[n2l];
        }
        while (true) {
            // 判断交差大于
            if (n1r < nums1.length && n2l >= 0 && nums1[n1r] < nums2[n2l]) {
                n1l++;
                n1r++;
                n2l--;
                n2r--;
            } else if (n1l >= 0 && n2r < nums2.length && nums2[n2r] < nums1[n1l]) {
                n1l--;
                n1r--;
                n2l++;
                n2r++;
            } else {
                break;
            }

        }
        //左边要取最大值，所以赋值最小值
        int ln1 = n1l == -1 ? Integer.MIN_VALUE : nums1[n1l];
        int ln2 = n2l == -1 ? Integer.MIN_VALUE : nums2[n2l];
        //右边要取最小值，所以赋值最大值
        int rn1 = n1r == nums1.length ? Integer.MAX_VALUE : nums1[n1r];
        int rn2 = n2r == nums2.length ? Integer.MAX_VALUE : nums2[n2r];

        int ln = Math.max(ln1, ln2);
        int rn = Math.min(rn1, rn2);
        return flag ? (ln + rn) / 2.0 : ln;
    }

    /**
     * O（1）
     */
    public static double findMedianSortedArraysO1(int[] nums1, int[] nums2) {
        //索引下标
        int i1 = 0;
        int i2 = 0;
        int count = nums1.length + nums2.length;
        int avg = count / 2;
        //是否为偶数和
        boolean flag = count % 2 == 0;
        int c = 0;
        int l = 0;
        while (i1 < nums1.length || i2 < nums2.length) {
            if (i2 >= nums2.length || (i1 < nums1.length && nums1[i1] < nums2[i2])) {
                l = c;
                c = nums1[i1];
                i1++;
            } else {
                l = c;
                c = nums2[i2];
                i2++;
            }
            if (i1 + i2 - 1 == avg) {
                break;
            }
        }
        return flag ? (c + l) / 2.0 : c;
    }


}
